package q1231_maximizeSweetness;

public class Solution {
    /*
    针对本题目：想要让分得的巧克力中总甜度最小的一块尽可能大。
    那么可以想到应该尽可能让它接近总甜度的均值
    但是还有限制条件：最终分得的巧克力数 k+1
    考虑到上述情况，那么我们最终的目标就是，
    在[0,avgSweetSum]中找到一个尽可能大的值x，使得当总甜度最小的巧克力块的总甜度>=x时能分出多于k+1块巧克力；

    结合我们的目标和二分查找的特点，可以得到以下方案：
    1 查找的对象为[0,avgSweetSum]的数组；
    2 判断标准为以当前总甜度作为总甜度最小的巧克力块的总甜度，是否能分出多于k+1块巧克力块，能，则下界移动，否则上界移动；

     */
    public int maximizeSweetness(int[] sweetness, int k) {
        int sumSw = 0;
        for (int j : sweetness) sumSw += j;

        int avg = sumSw / (k + 1);
        int l = 0,r = avg;
        while(l <= r){
            int mid = (r - l)/2 + l;
            if(isFeasible(mid, k, sweetness)) l = mid + 1;
            else r = mid - 1;
        }
        return r;

    }

    /*
    此方法用来判断当前我们设计的甜度阈值能否满足分出来k+1个的条件
    在循环中 我们用一个sum 我们不断的把巧克力放到sum中直到它超过我们的阈值 此时就相当于打包出来一份巧克力
    然后sum归零 count++ 继续打包下一份
     */
    public boolean isFeasible(int minDiv, int k, int[] sweetness){
        int count = 0,sum = 0;
        for(int x : sweetness){
            sum += x;
            if(sum >= minDiv){
                sum = 0;
                count++;
            }
        }
        return count >= k + 1;
    }

}
